﻿using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using C5;

namespace GISCore.Geometry.Intersectors
{   
    public class SweepLine : IIntersector
    {
        public SweepLine() { }

        public IEnumerable<IntersectPoint> Intersect(IEnumerable<Line> lines)
        {
            Debug.Assert(lines != null);

            return SweepLine.Sweep(lines);
        }

        /// <summary>
        /// Runs a sweep line along a list of line segments to determine intersection points
        /// </summary>
        /// <param name="lines">the list of line segments</param>
        /// <returns>the intersection points</returns>
        private static List<IntersectPoint> Sweep(IEnumerable<Line> lines)
        {
            Debug.Assert(lines != null);

            var intersections = new System.Collections.Generic.HashSet<IntersectPoint>();
            EventQueue eventQueue = new EventQueue(lines);
            StatusTree statusTree = new StatusTree();            

            while (!eventQueue.IsEmpty)
            {
                var eventPair = eventQueue.DeleteMin();
                var ps = _handleEventPoint(eventPair, eventQueue, statusTree);
                ps.ForEach((p) => intersections.Add(p));
            }
            return intersections.ToList();
        }

        /// <summary>
        /// Takes an eventpoint to determine if there are any new intesections
        /// </summary>
        /// <param name="eventPair">The eventpair that conaints the evenpoint and the lines of which it is the upper endpoint</param>
        /// <param name="eventQueue">The eventqueue of points</param>
        /// <param name="statusTree">The status tree of the current order of segments</param>
        /// <returns>a new intersection point</returns>
        private static List<IntersectPoint> _handleEventPoint(EventQueue.EventPair eventPair, EventQueue eventQueue, StatusTree statusTree)
        {
            Debug.Assert(eventPair != null && eventQueue != null && statusTree != null);

            Point eventPoint = eventPair.EventPoint; // the event point itself
            IntersectPoint inter;
            List<IntersectPoint> inters = new List<IntersectPoint>();
            List<Line> U_p = eventPair.EventLines;   // the list of lines whose upper point is the event point
            List<Line> L_p = new List<Line>();
            List<Line> C_p = new List<Line>();
            Line left;
            Line right;

            // find the lines where the eventpoint is the lower point
            // or where the event point is an intersection point
            statusTree.FindLines(eventPoint, ref L_p, ref C_p);

            // remove segments in L-p from ST because they will not be considered after this round
            // we delete and reinsert the segments of C-p to reverse the order of them
            // because they have crossed sides with the sweep line
            // example: if x is the event point, the ordering of A and B must switch after this
            //      A    B
            //      \   /
            //       \ /
            //        x
            //       / \
            //      /   \
            statusTree.DeleteAll(L_p);
            statusTree.DeleteAll(C_p);

            foreach (Line l in U_p)
            {
                l.SweepPoint = eventPoint;
                statusTree.Insert(l);
            }
            foreach (Line l in C_p)
            {
                l.SweepPoint = eventPoint;
                statusTree.Insert(l);
            }
            
            if (U_p.Count + C_p.Count == 0)
            {
                statusTree.GetNeighbors(eventPoint, out left, out right);
                if (_findNewEvent(left, right, eventPoint, eventQueue, out inter))
                {
                    _addIntersection(inter, inters, left, right);
                }
            }
            else
            {
                Line leftPrime = _getLeftMost(U_p, C_p);
                statusTree.GetNeighbors(leftPrime, out left, out right);
                if (_findNewEvent(left, leftPrime, eventPoint, eventQueue, out inter))
                {
                    _addIntersection(inter, inters, left, leftPrime);
                }
                Line rightPrime = _getRightMost(U_p, C_p);                
                statusTree.GetNeighbors(rightPrime, out left, out right);
                if (_findNewEvent(right, rightPrime, eventPoint, eventQueue, out inter))
                {
                    _addIntersection(inter, inters, right, rightPrime);
                }
            }
            return inters;
        }

        private static void _addIntersection(IntersectPoint inter, List<IntersectPoint> inters, Line left, Line leftPrime)
        {
            if (inter != null)
            {
                left.AddIntersection(inter);
                leftPrime.AddIntersection(inter);
                inters.Add(inter);
            }
        }

        /// <summary>
        /// Retrieves the rightmost line segment out of the two collections
        /// </summary>
        /// <param name="L_p"></param>
        /// <param name="C_p"></param>
        /// <returns></returns>
        private static Line _getRightMost(List<Line> L_p, List<Line> C_p)
        {
            Func<Line, Line, Line> rightMost = (a, b) => (a.Right.X > b.Right.X) ? a : b;

            return _getMost(L_p, C_p, rightMost);          
        }

        /// <summary>
        /// Retrieves the leftmost line segment out of the two collections
        /// </summary>
        /// <param name="L_p"></param>
        /// <param name="C_p"></param>
        /// <returns></returns>
        private static Line _getLeftMost(List<Line> L_p, List<Line> C_p)
        {
            Func<Line, Line, Line> leftMost = (a, b) => (a.Left.X < b.Left.X) ? a : b;
            
            return _getMost(L_p, C_p, leftMost);
        }

        /// <summary>
        /// Generalization of finding the 'most' something between the two lists
        /// </summary>
        /// <param name="L_p"></param>
        /// <param name="C_p"></param>
        /// <param name="aggregator">aggregate function to take two lines, compare, then return the line that is 'more something'</param>
        /// <returns></returns>
        private static Line _getMost(List<Line> L_p, List<Line> C_p, Func<Line, Line, Line> aggregator)
        {
            Line l = L_p.Count > 0 ? L_p.Aggregate(aggregator) : null;
            Line c = C_p.Count > 0 ? C_p.Aggregate(aggregator) : null;
            Line retval = null;

            if (l != null)
            {
                retval = (c != null) ? aggregator(l, c) : l;
            }
            else
            {
                retval = c;
            }

            return retval;
        }

        /// <summary>
        /// Determines if there is a new event point (intersection)
        /// </summary>
        /// <param name="left">left line</param>
        /// <param name="right">right line</param>
        /// <param name="eventPoint">current event point</param>
        /// <param name="eventQueue">event queue to place new event points</param>
        /// <returns>the new event point</returns>
        private static bool _findNewEvent(Line left, Line right, Point eventPoint, EventQueue eventQueue, out IntersectPoint inter)
        {
            bool inserted = false;
            inter = null;
            if (left != null && right != null)
            {
                if (left.getIntersect(right, out inter) == Intersection.True)
                {
                    // these are properties of the total ordering that must hold for this
                    // to be a valid intersection
                    if (inter.Y < eventPoint.Y || (inter.Y == eventPoint.Y && inter.X > eventPoint.X))
                    {
                        inserted = eventQueue.Add(inter, null);
                        if (inserted)
                        {
                            inter.inComingLine = right;
                            right.addPoint(inter);
                            inter.outGoingLine = left;
                            left.addPoint(inter);
                        }
    
                        if (!inserted)
                            inter = null;
                    }
                    else
                    {
                        inter = null;
                    }
                }
                                
            }
            return inserted;
        }

        /// <summary>
        /// The EventQueue will maintain the order of events to handle.
        /// The order on event points is defined as the following:
        ///     Given points p and q, p < q IFF
        ///         p_y > q_y holds OR
        ///         p_y == q_y and p_x < q_x
        /// </summary>
        private class EventQueue
        {
            private TreeDictionary<Point, List<Line>> _eq;

            public EventQueue(IEnumerable<Line> lines)
            {
                Debug.Assert(lines != null);

                _eq = new TreeDictionary<Point, List<Line>>(new EventPointComparer());
                var epc = new EventPointComparer();

                // as we add the point/line pairs only add the lines
                // to the upper points. leftmost point is for tiebreaking
                foreach (var line in lines)
                {
                    int result = epc.Compare(line.Start, line.End);
                    switch (result)
                    {
                        case -1:
                            this.Add(line.Start, line);
                            this.Add(line.End, null);
                            break;
                        case 0:
                        case 1:
                            this.Add(line.Start, null);
                            this.Add(line.End, line);
                            break;
                    }
                }
            }

            public bool Add(Point p, Line line)
            {
                Debug.Assert(p != null);
                bool inserted = false;

                if (!_eq.Contains(p))
                {
                    _eq.Add(p, new List<Line>());
                    inserted = true;
                }

                if (line != null)
                {
                    _eq[p].Add(line);
                }
                return inserted;
            }

            public EventPair DeleteMin()
            {
                Debug.Assert(!_eq.IsEmpty);

                var t = _eq.DeleteMin();
                return new EventPair(t.Key, t.Value);
            }

            public bool IsEmpty { get { return _eq.IsEmpty; } }

            public override string ToString()
            {
                return _eq.ToString();
            }

            /// <summary>
            /// The order on event points is defined as the following:
            ///     Given points p and q, p < q IFF
            ///         p_y > q_y holds OR
            ///         p_y == q_y and p_x < q_x
            /// </summary>
            private class EventPointComparer : IComparer<Point>
            {
                public int Compare(Point a, Point b)
                {
                    int val = 0;
                    if (a.Y > b.Y)
                    {
                        val = -1;
                    }
                    else if (a.Y < b.Y)
                    {
                        val = 1;
                    }
                    else
                    {
                        if (a.X < b.X)
                        {
                            val = -1;
                        }
                        else if (a.X > b.X)
                        {
                            val = 1;
                        }
                        else
                        {
                            val = 0;
                        }
                    }
                    return val;
                }
            }

            public class EventPair
            {
                public Point EventPoint { get; private set; }
                public List<Line> EventLines { get; private set; }

                public EventPair(Point p, List<Line> lines)
                {
                    EventPoint = p;
                    EventLines = lines;
                }
                public override string ToString()
                {
                    return string.Format("{0} => {1}", EventPoint, EventLines);
                }
            }
        }

        /// <summary>
        /// The StatusTree will maintain the state of the algorithm. It is a left to right ordering of the points.
        /// </summary>
        private class StatusTree
        {
            private TreeSet<Line> _tree;

            public StatusTree()
            {
                _tree = new TreeSet<Line>(new StatusLineComparer());
            }

            /// <summary>
            /// This will find certain lines that contain the event point
            /// </summary>
            /// <param name="eventPoint">the eventpoint to be used for membership</param>
            /// <param name="L_p">all lines that contain the eventpoint as its lower point</param>
            /// <param name="C_p">all lines that contain the eventpoint as an interion point (intersection)</param>
            public void FindLines(Point eventPoint, ref List<Line> L_p, ref List<Line> C_p)
            {
                Debug.Assert(eventPoint != null);
                L_p = _tree.FindAll((l) => l.Lower.Equals(eventPoint)).ToList();
                C_p = _tree.FindAll((l) => l.ContainsIntersection(eventPoint)).ToList();
            }

            /// <summary>
            /// this will remove all lines in L-p associated with eventPoint
            /// </summary> 
            /// <param name="L_p">the list of lines that contain the eventpoint as an lower point</param>
            public void DeleteAll(List<Line> lines)
            {
                Debug.Assert(lines != null);
                _tree.RemoveAll<Line>(lines);
            }

            /// <summary>
            /// this will add a line with the associated eventpoint
            /// </summary>
            /// <param name="line">the line to add</param>
            /// <returns>if the line was inserted</returns>
            public bool Insert(Line line)
            {
                Debug.Assert(line != null);
                return _tree.Add(line);
            }

            /// <summary>
            /// this will get the immediate left and right neighbor lines of the eventpoint
            /// </summary>
            /// <param name="eventPoint"></param>
            /// <param name="left"></param>
            /// <param name="right"></param>
            public void GetNeighbors(Point eventPoint, out Line left, out Line right)
            {
                Debug.Assert(eventPoint != null);
                //this is a trick to make a line, that really is just a point
                Line tmp = new Line(eventPoint, eventPoint);
                GetNeighbors(tmp, out left, out right);
            }

            public void GetNeighbors(Line line, out Line left, out Line right)
            {
                Debug.Assert(line != null);
                if (!_tree.TryPredecessor(line, out left))
                {
                    if (!_tree.TryWeakPredecessor(line, out left))
                    {
                        left = null;
                    }
                }
                if (!_tree.TrySuccessor(line, out right))
                {
                    if (!_tree.TryWeakSuccessor(line, out right))
                    {
                        right = null;
                    }
                }
            }

            public override string ToString()
            {
                return _tree.ToString();
            }

            private class StatusPointComparer : IComparer<Point>
            {
                public int Compare(Point x, Point y)
                {
                    return (x.X < y.X) ? -1 : (x.X == y.X) ? 0 : 1;
                }
            }
            /// <summary>
            /// Comparer class for two lines
            /// Given lines n,m:
            ///     n < m iff:
            ///         n.Left < m.Left OR
            ///         n.Left = m.Left, n.Right < m.Right
            /// </summary>
            private class StatusLineComparer : IComparer<Line>
            {
                public int Compare(Line x, Line y)
                {                    
                    var spc = new StatusPointComparer();
                    int value = spc.Compare(x.SweepPoint, y.SweepPoint);
                    // if left points for both lines are equal
                    // break ties with the right point
                    if (value == 0)
                    {
                        value = spc.Compare(x.Lower, y.Lower);
                        if (value == 0)
                        {
                            value = x.Equals(y) ? 0 : -1;
                        }
                    }

                    return value;
                }
            }
        }
    }
}
